//
// Created by 85792 on 24-5-19.
//
#ifndef CMM_COMPILER_SYNTAX_OLD_H
#define CMM_COMPILER_SYNTAX_OLD_H

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iterator>
#include <utility>
#define DEBUG
using namespace std;
const int N = 100;

/*SYMBOL VARIABLES*/
set<string> Vn, Vt;          // set of non-terminal symbols and terminal symbols
map<string, int> vnMap;      // [symbol -> id] map of set Vn
map<string, int> vtMap;      // [symbol -> id] map of set Vt
map<string, int> vMap;       // [symbol -> id] map of symbols
map<int, string> vMapI;      // [symbol -> id] inverse map of symbols
vector<vector<string>> v[N]; // [left symbols] -> vec(expressions) -> vec(right symbols)
int cnt_vn;                  // number of non-terminal symbols
int cnt_vt;                  // number of terminal symbols
int cnt_v;                   // number of symbols

/*FIRST AND FOLLOW VARIABLES*/
map<string, set<string>> first = {{"$", set<string>{"$"}}};        // first set ($ -> {$})
map<string, set<string>> follow = {{"program", set<string>{"#"}}}; // follow set (program -> {#})

/*TABLE VARIABLES*/
pair<int, int> table[N][N];              // NxN table, each element is a pair of int
const pair<int, int> tab_init = {0, -1}; // initialize pair

/*ANALYSIS VARIABLES*/
vector<string> in_symbol; // symbols to analyse
string stack[N];          // symbol stack
int top;                  // stack top
int analysis_no;          // analysis step count

/*FILES*/
const char grammar_file[] = "grammar.txt";   // path to the grammar.txt file
const char input_file[] = "result.txt";    // file to analyse
const char syntax_file[] = "doSyntaxAnalysis.txt"; // output analysis file
const char first_file[] = "first.txt";           // output first file
const char follow_file[] = "follow.txt";         // output follow file
const char table_file[] = "table.txt";           // output table file

/*----------READ GRAMMAR AND GET VN AND VT----------*/
void getVnVt() {
    FILE *fp = freopen(grammar_file, "r", stdin);
    char c;
    vector<string> *right_vec; // stores every symbol of an expression
    string cur_symbol = "";
    bool isLeft = 1;
    int id;
    string str = "";
    int line = 0;
    while ((c = getchar()) != EOF) {
        // end line (5th)
        if (c == '\n') {
            Vt.insert(cur_symbol);            // insert into Vt
            right_vec->push_back(cur_symbol); // push into right_vec
            v[id].push_back(*right_vec);      // push expression (has right_vec symbols) into left symbol
            isLeft = 1;
            cur_symbol = ""; // reset symbol
            continue;
        }
        // sees a char
        if (c != ' ' && c != '\t') {
            cur_symbol += c; // add each char to form a string (symbol)
            continue;
        }
            // sees " " or "/t"
        else {
            // if " " or "/t", next loop (2nd)
            if (cur_symbol == "")
                continue;
            // if "->", reset symbol and next loop (3rd)
            if (cur_symbol == "->") {
                isLeft = 0;
                cur_symbol = "";
            }
                // left symbol (run this 1st)
            else if (isLeft) {
                id = vMap[cur_symbol]; // get symbol id from map
                // if symbol is new
                if (id == 0) {
                    id = ++cnt_v;
                    vMap[cur_symbol] = id;
                    vMapI[id] = cur_symbol;
                }
                Vn.insert(cur_symbol);          // insert into Vn
                right_vec = new vector<string>; // create right symbols vector
                cur_symbol = "";                // reset symbol
            }
                // right_vec symbol (4th)
            else {
                right_vec->push_back(cur_symbol); // push into right_vec
                Vt.insert(cur_symbol);            // insert into Vt
                cur_symbol = "";
            }
        }
    }
    // remove symbols that are non-terminal in Vt
    for (string token: Vn)
        Vt.erase(token);
    fclose(fp);
}

/*----------GET FIRST SET OF EACH SYMBOLS----------*/
void getFirst(string token) {
//    cout<<token<<endl;
    // if first(token) exists
    if (first.count(token) > 0)
        return;
    // (1) if token is terminal, first(token) = token
    if (Vt.count(token)) {
        set<string> temp_set;
        temp_set.insert(token);
        first[token] = temp_set;
        return;
    }
    int id = vMap[token]; // get token id
    vector<vector<string>> token_id = v[id];
    set<string> temp_set; // temp set
    // iterate every expression of the token
    for (int i = 0; i < token_id.size(); i++) {
        vector<string> exp = token_id[i];
        bool AllHasE = 1; // every symbols leads to $
        // iterate every symbol in the expression
        for (string str: exp) {
            getFirst(str); // get first(symbol) (recursively)
            set<string> first_str = first[str];
            bool hasE = 0;
            // iterate first(symbol)
            for (string sym: first_str) {
                // if leads to $
                if (sym == "$") {
                    hasE = 1;
                }
                    // (2)(3) insert to temp set
                else {
                    temp_set.insert(sym);
                }
            }
            // if first(current symbol) do not lead to $
            if (!hasE) {
                AllHasE = 0;
                break;
            }
        }
        // (3) add $ into temp set if first of all expressions lead to $
        if (AllHasE)
            temp_set.insert("$");
    }
    first[token] = temp_set; // put temp set into first(token)
    // continue getting first of the symbols that the token can express (recursively)
    for (int i = 0; i < v[id].size(); i++) {
        vector<string> exp = v[id][i];
        for (string str: exp) {
            getFirst(str);
        }
    }
}

/*----------GET FOLLOW SET OF EACH NON-TERMINAL SYMBOLS----------*/
bool getFollow() {
    // return whether the follow set updated
    bool updated = false;
    // iterate every non-terminal symbol
    for (string token: Vn) {
        // if token has no follow set yet
        if (follow.count(token) == 0) {
            set<string> temp_set;
            follow[token] = temp_set;
        }
        set<string> temp_set = follow[token]; // temp set = follow set
        int size_before = temp_set.size();
        // iterate every non-terminal symbol
        for (int i = 1; i <= cnt_v; i++) {
            vector<vector<string>> token_id = v[i];
            // iterate every expression of the symbol
            for (int j = 0; j < token_id.size(); j++) {
                vector<string> exp = token_id[j]; // get expression
                bool found = false;
                bool hasNoE = false;
                // iterate every symbol in the expression
                for (string str: exp) {
                    if (found) {
                        set<string> first_str = first[str]; // get first(symbol)
                        bool hasE = false;
                        // iterate first(symbol)
                        for (string sym: first_str) {
                            // if leads to $
                            if (sym == "$")
                                hasE = true;
                                // (2) insert into temp set
                            else
                                temp_set.insert(sym);
                        }
                        // if first(current symbol) do not lead to $
                        if (!hasE) {
                            hasNoE = true;
                            break;
                        }
                    }
                    // eg. Follow(B) = First(B) so need to find
                    if (str == token)
                        found = true;
                }
                // if first of all symbols lead to $
                if (!hasNoE && found) {
                    string head = vMapI[i]; // get follow(left symbol)
                    if (!follow.count(head))
                        continue;
                    set<string> curset = follow[head];
                    // (3) insert follow(left symbol) into temp set
                    for (string cur: curset) {
                        temp_set.insert(cur);
                    }
                }
            }
        }

        // update follow(token)
        if (temp_set.size() != size_before) {
            follow[token] = temp_set;
            updated = true;
        }
    }
    return updated;
}

/*----------GET PREDICTIVE ANALYSIS TABLE----------*/
bool getTable0() {
    // give index to every non-terminal symbols
    cnt_vn = 0;
    for (string token: Vn) {
        vnMap[token] = ++cnt_vn;
    }
    // give index to every terminal symbols
    cnt_vt = 0;
    Vt.insert("#");
    for (string token: Vt) {
        vtMap[token] = ++cnt_vt;
    }
    // initialize every table index to (0, -1)
    for (int i = 0; i <= cnt_vn; i++) {
        for (int j = 0; j <= cnt_vt; j++) {
            table[i][j] = tab_init;
        }
    }
    bool wrong = false; // return value
    // iterate every token(non-terminal symbol)
    for (string token: Vn) {
#ifdef DEBUG
        cout<<endl<<token<<endl;
#endif
        int nid = vMap[token]; // get id
        bool hasE = false;
        // iterate every expression of the symbol
        for (int i = 0; i < v[nid].size(); i++) {
            set<string> temp_set;           // temp set
            vector<string> exp = v[nid][i]; // get expression
            bool theE = true;
#ifdef DEBUG
            cout<<"-->";
            for (string s: exp) {
                cout<<" "<<s;
            }
            cout<<endl;
#endif
            // iterate every symbol in the expression
            for (string str: exp) {
                bool hasNotE = true;
                set<string> first_str = first[str]; // get first(symbol)
#ifdef DEBUG
                cout<<"(1) "<<str<<"::";
                for(string s:first_str) {
                    cout<<s<<" ";
                }
                cout<<endl;
#endif
                // iterate first(symbol)
                for (string sym: first_str) {
                    // if leads to $
                    if (sym == "$") {
                        hasNotE = false;
                        continue;
                    }
                    // insert into temp set
                    temp_set.insert(sym);
                }
                // if first(current symbol) do not lead to $
                if (hasNotE) {
                    theE = false;
                    break;
                }
            }
#ifdef DEBUG
            cout<<"(2) temp::";
            for(string s:temp_set) {
                cout<<s<<" ";
            }
            cout<<endl;
#endif
            // (2) iterate every symbol in temp set
            for (string sym: temp_set) {
                int tid = vtMap[sym]; // get column (a)
                // if conflicted, wrong
#ifdef DEBUG
                cout<<"sym:"<<sym<<", tokenId:"<<nid<<", column:"<<tid<<", first:"<<table[nid][tid].first<<", second:"<<table[nid][tid].second<<endl;
#endif
                if (table[nid][tid] != tab_init) {
                    wrong = true;
                    return wrong;
                }
                // M[A,a], give current expression to the index (row = non-term, col = term)
                table[nid][tid] = {nid, i};
            }
            // if first of all symbols lead to $
            if (theE)
                hasE = true;
        }
        // if current token leads to $
        if (hasE) {
            set<string> follow_token = follow[token]; // get follow(token)
            // (3) iterate every symbol in follow
#ifdef DEBUG
            cout<<"follow: ";
            for(string s:follow_token) {
                cout<<s<<" ";
            }
            cout<<endl;
#endif
            for (string sym: follow_token) {
                int tid = vtMap[sym]; // get column (b)
                // if conflicted, wrong
#ifdef DEBUG
                cout<<"sym:"<<sym<<", tokenId:"<<nid<<", column:"<<tid<<", first:"<<table[nid][tid].first<<", second:"<<table[nid][tid].second<<endl;
#endif
                if (table[nid][tid] != tab_init) {
//                    wrong = true;
//                    return wrong;
                    continue;
                }
                // M[A,b], give -> $ expression to the index (row = non-term, col = term)
                table[nid][tid] = {nid, N - 1};
            }
        }
    }
    return wrong;
}

/*----------GET SYMBOLS FROM LEXICAL FILE----------*/
void getSymbols(string str) {
    string c1 = "", c2 = "", c3 = "";
    int index = 0;
    // c1 gets actual value (a, 10, int)
    while (str[index] != ' ' && str[index] != '\t')
        c1 += str[index++];
    while (str[index] == ' ' || str[index] == '\t')
        index++;
    index++;
    // c2 gets data type (INT, IDN, KW)
    while (str[index] != ',')
        c2 += str[index++];
    index++;
    // c3 gets index of data type
    while (str[index] != '>')
        c3 += str[index++];
    // if c1 is variable or number, push c2 instead
//    if (c2 == "IDN")
//        in_symbol.push_back("Ident");
//    else
    if (c2 == "INT" || c2 == "IDN" || c2 == "FLOAT")
        in_symbol.push_back(c2);
    else
        in_symbol.push_back(c1);
}

/*----------ANALYSE LEXICAL FILE----------*/
bool getAnalysis() {
    FILE *fp = freopen(syntax_file, "w", stdout);
    auto symbol_it = in_symbol.begin(); // in_symbol iterator
    while (1) {
        string token = stack[top - 1];
        // if stack top is terminal symbol
        if (Vt.count(token)) {
            // if stack top == current char, MOVE
            if (token == *symbol_it) {
                // end of analysis
                if (token == "#") {
                    cout << ++analysis_no << " \t" << token << "#" << *symbol_it << "\t"
                         << "accept" << endl;
                    fflush(fp);
                    fclose(fp);
                    freopen("CON", "w", stdout);
                    return true;
                } else {
                    cout << ++analysis_no << " \t" << token << "#" << *symbol_it << "\t"
                         << "move" << endl;
                    top--, symbol_it++; // stack pop, next char
                }
            }
                // error
            else {
                cout << ++analysis_no << " \t" << token << "#" << *symbol_it << "\t"
                     << "error" << endl;
                fflush(fp);
                fclose(fp);
                freopen("CON", "w", stdout);
                return false;
            }
        }
            // if stack top is non-terminal symbol
        else {
            int nid = vMap[token];
            int tid = vtMap[*symbol_it];
            // if table[token][char] is empty, error
            if (table[nid][tid].second == -1) {
                cout << ++analysis_no << " \t" << token << "#" << *symbol_it << "\t"
                     << "error" << endl;
                fflush(fp);
                fclose(fp);
                freopen("CON", "w", stdout);
                cout << "error detail: " << endl;
                cout << "stack top: " << token << "(" << nid << ")" << endl;
                cout << "input symbol: " << *symbol_it << "(" << tid << ")" << endl;
                cout << endl;
                return false;
            }
                // if table[token][char] has expression, REDUCTION
            else {
                cout << ++analysis_no << " \t" << token << "#" << *symbol_it << "\t"
                     << "reduction" << endl;
                top--;                              // stack pop
                int expId = table[nid][tid].second; // get expression id
                if (expId == 99)                    // if leads to $
                    continue;
                vector<string> str = v[nid][expId];
                for (int i = str.size() - 1; i >= 0; i--) {
                    stack[top++] = str[i]; // reverse stack push the symbols
                }
            }
        }
    }
}

/*----------ANALYSE LEXICAL FILE USING GET-SYMBOLS AND GET-ANALYSIS----------*/
bool analysis() {
    stack[top++] = "#";
    stack[top++] = "program";
    FILE *fp = freopen(input_file, "r", stdin);
    char c;
    string str = "";
    while ((c = getchar()) != EOF) {
        if (c == '\n') {
            getSymbols(str);
            str = "";
            continue;
        }
        str += c; // get a line from file, and extract in_symbol using getSymbols
    }
    fclose(fp);
    in_symbol.push_back("#"); // analysis ends with #
    return getAnalysis();
}

void print_first() {
    FILE *fp = freopen(first_file, "w", stdout);
    for (string token: Vn) {
        set<string> first_token = first[token];
        cout << token << ": ";
        for (string str: first_token)
            cout << str << " ";
        cout << endl;
    }
    fflush(fp);
    fclose(fp);
    freopen("CON", "w", stdout);
}

void print_follow() {
    FILE *fp = freopen(follow_file, "w", stdout);
    for (string token: Vn) {
        set<string> follow_token = follow[token];
        cout << token << ": ";
        for (string str: follow_token)
            cout << str << " ";
        cout << endl;
    }
    fflush(fp);
    fclose(fp);
    freopen("CON", "w", stdout);
}

void print_table() {
    FILE *fp = freopen(table_file, "w", stdout);
    cout << "\t\t";
    for (string str: Vt) {
        cout << str << "\t";
    }
    cout << endl;
    for (string token: Vn) {
        int nid = vMap[token];
        cout << token << "\t";
        for (string str: Vt) {
            int tid = vtMap[str];
            cout << table[nid][tid].second << "\t";
        }
        cout << endl;
    }
    fflush(fp);
    fclose(fp);
    freopen("CON", "w", stdout);
}

void syn_main() {
    getVnVt();
    cout << "Successfully read and analyse Vt and Vn from grammar.txt.\n" << endl;

    getFirst("program");
    cout << "Successfully created first sets.\n" << endl;
    print_first();

    while (getFollow());
    cout << "Successfully created follow sets.\n" << endl;
    print_follow();

    if (getTable0()) {
        puts("Grammar is not LL(1)\n");
        exit(0);
    }
    cout << "Successfully created predictive analysis table.\n" << endl;
    print_table();

    if (!analysis()) {
        puts("The analysis has error(s).\n");
    }
    cout << "Analysis of input.txt completed.\n" << endl;
}
#endif //CMM_COMPILER_SYNTAX_OLD_H
